package com.c2b.algorithm.leetcode.jzofferII;

/**
 * <a href="https://leetcode.cn/problems/2VG8Kg/">和大于等于 target 的最短子数组</a>
 * <p>
 * 给定一个含有 n 个正整数的数组和一个正整数 target 。<br>
 * 找出该数组中满足其和 ≥ target 的长度最小的 连续子数组 [numsl, numsl+1, ..., numsr-1, numsr] ，并返回其长度。如果不存在符合条件的子数组，返回 0 。
 * </p>
 *
 * <pre>
 * 示例 1：
 *      输入：target = 7, nums = [2,3,1,2,4,3]
 *      输出：2
 *      解释：子数组 [4,3] 是该条件下的长度最小的子数组。
 *
 * 示例 2：
 *      输入：target = 4, nums = [1,4,4]
 *      输出：1
 *
 * 示例 3：
 *      输入：target = 11, nums = [1,1,1,1,1,1,1,1]
 *      输出：0
 * </pre>
 * <b>提示：</b>
 * <ui>
 * <li>1 <= target <= 10^9</li>
 * <li>1 <= nums.length <= 10^5</li>
 * <li>1 <= nums[i] <= 10^5</li>
 * </ui>
 *
 * @author c2b
 * @since 2023/4/12 17:57
 */
public class Jz008MinSubArrayLen_M {
    /**
     * 双指针
     */
    public int minSubArrayLen(int target, int[] nums) {
        int res = nums.length + 1;
        int slowIndex = 0;
        int fastIndex = 0;
        int sum = 0;
        while (fastIndex < nums.length) {
            sum += nums[fastIndex];
            // 找到符合的数字
            while (sum >= target) {
                // 更新最小数量
                res = Math.min(res, fastIndex - slowIndex + 1);
                // 尝试缩小范围
                sum -= nums[slowIndex];
                ++slowIndex;
            }
            ++fastIndex;
        }
        return res == nums.length + 1 ? 0 : res;
    }


    public int minSubArrayLen2(int target, int[] nums) {
        int res = Integer.MAX_VALUE;
        for (int i = 0; i < nums.length; i++) {
            int sum = nums[i];
            int tempRes = 1;
            if (sum >= target) {
                res = res == 0 ? tempRes : Math.min(res, tempRes);
            }
            for (int j = i + 1; j < nums.length; j++) {
                sum += nums[j];
                tempRes++;
                if (sum >= target) {
                    // 更新res
                    res = res == 0 ? tempRes : Math.min(res, tempRes);
                    break;
                }
            }
        }
        return res == Integer.MAX_VALUE ? 0 : res;
    }

    public static void main(String[] args) {
        Jz008MinSubArrayLen_M jzOfferMinSubArrayLen_m = new Jz008MinSubArrayLen_M();
        int i = jzOfferMinSubArrayLen_m.minSubArrayLen(7, new int[]{2, 3, 1, 2, 4, 3});
        System.out.println(i);
    }
}
